package a快排;

import java.util.List;

public class Solution {
    public void quickSort(List<Integer> list,int low,int high){
        int i,j,temp,t;
        if(low>high){
            return;
        }
        i=low;
        j=high;
        //temp就是基准位
        temp = list.get(low);

        while (i<j) {
            //先看右边，依次往左递减
            while (temp <= list.get(j) && i < j) {
                j--;
            }
            //再看左边，依次往右递增
            while (temp >= list.get(i) && i < j) {
                i++;
            }
            //如果满足条件则交换
            if (i<j) {
                t = list.get(j);
                list.set(j,list.get(i));
                list.set(i,t);
            }

        }
        //最后将基准为与i和j相等位置的数字交换
        list.set(low,list.get(i));
        list.set(i,temp);
        //递归调用左半数组
        quickSort(list, low, j-1);
        //递归调用右半数组
        quickSort(list, j+1, high);
    }
}
